/**
 * @author LKQ
 * @date 2022/1/29 13:43
 * @description 动态规划 f(n, k) = f(n-1, k) + k
 */
public class FormalSolution2 {
    public static void main(String[] args) {
        FormalSolution2 formalSolution2 = new FormalSolution2();
        formalSolution2.findTheWinner(5, 2);
    }
    public int findTheWinner(int n, int k) {
        // f[i] 表示有i个数轮k后的幸存者，那么f[i+1]就是f[i]偏移k位后的数(即幸存者)
        int[] f = new int[n + 1];
        f[1] = 1;
        for(int i = 2; i <= n; i++) {
            // f[i-1] + k即为偏移量，为防止刚好整除的情形导致取模为0，对原值-1后再对模+1.
            f[i] = ((f[i-1] + k - 1) % i) + 1;
        }
        return f[n];
    }

}
